package org.skywork.top.core.algorithm.tree;

import org.skywork.top.core.algorithm.support.TreeNode;

/**
 * 二叉树的最大深度
 */
public class no_104 {


    /**
     * 给定一个二叉树 root ，返回其最大深度。
     *
     * 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
     */
    public int maxDepth(TreeNode root) {

        /**
         * 示例 1：
         * 输入：root = [3,9,20,null,null,15,7]
         * 输出：3
         *
         *
         * 示例 2：
         * 输入：root = [1,null,2]
         * 输出：2
         */
        if(root == null){
            return 0;
        }

        if(root.left == null && root.right == null){
            return 1;
        }

        return depth(root, 1);
    }

    public int depth(TreeNode node, int num){
        int left = num;
        if(node.left != null){
            left++;
            left = depth(node.left, left);
        }
        int right = num;
        if(node.right != null){
            right++;
            right = depth(node.right, right);
        }
        return Math.max(left, right);
    }

}
